package leetcode每日一题.leetcode20213;

/**
 * 1. 问题描述
 *      求出32位二进制中的1的个数
 *
 * 2. 算法分析
 *      1. 循环位运算模拟实现
 *         具体的思路如下：
 *              主要是通过与性质来实现，假设当前我们设置一个掩码 mask = 0000 0000 0000 0000 0000 0000 0000 0001(32位的1)
 *              ，实际上mask = 1(10进制)，我们对于与运算有如下的性质：
 *                  1 & x = 1  if x = 1
 *                  1 & x = 0  if x = 0
 *              由此我们通过mask可以判断出当前32位二进制数的从右开始第一位是否为1，然后对mask进行左移1位，左移之后，mask就会变为
 *              mask = 0000 0000 0000 0000 0000 0000 0000 0010(32位的2) 具体实现为 mask =>> 1,实际上mask = 2(10进制)
 *              重复上述步骤
 *              通过上述规律我们知道，mask的10进制取值为 2 ^ n     n = 0,1,2....,
 *
 *      2. 位操作的小技巧
 *
 * 3.代码实现
 */
@SuppressWarnings("all")
public class Q003_1_位1的个数 {

    /**
     *循环位运算    时间复杂度为O(32)  空间为O(1)
     * @param n
     * @return
     */
    public int hammingWeight1(int n) {
        int ones = 0;
        int mask = 1; // 设置掩码
        for(int i = 0; i < 32; i++) {
            // 注意此处的位运算需要加括号保证优先级
            if((mask & n) != 0) {
                ones++;
            }
            mask <<= 1;
        }
        return ones;
    }

    /**
     * 由于n为一个长为32位的二进制数，有0，有1，如果我们将n变为32位的0，主需要将n中所有的1变为0
     * 这样我们通过一个循环while(n != 0) 如果n此时不为0，让ones+1，问题是如何将n中的1全部变为0？
     * 考虑n与n-1之间的关系，我们知道n的最低位的1恰好对应于n-1的0，让n与n-1做与运算，我们就可以将n
     * 中最低位的1变为0，而其余不变(思考为什么其余不变?  )
     * @param n
     * @return
     */
    public int hammingWeight2(int n) {
        int ones = 0;
        while(n != 0) {
            ones++;
            n &= (n-1);
        }
        return ones;
    }
}
